package com.fanshuai2.niuke.matrix;

import java.util.Scanner;
import java.util.Stack;

/**
 * 矩阵乘法的运算量与矩阵乘法的顺序强相关。
 * 例如：
 *
 * A是一个50×10的矩阵，B是10×20的矩阵，C是20×5的矩阵
 *
 * 计算A*B*C有两种顺序：((AB)C)或者(A(BC))，前者需要计算15000次乘法，后者只需要3500次。
 *
 * 编写程序计算不同的计算顺序需要进行的乘法次数。
 * 输入：
 * 3
 * 50 10
 * 10 20
 * 20 5
 * (A(BC))
 * 复制
 * 输出：
 * 3500
 */
public class MatrixCount {
    static class Matrix {
        int x;
        int y;

        public Matrix(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static int getCount(Matrix[] m, String exp) {
        Stack<Matrix> stack = new Stack<>();
        int total = 0;

        int i = exp.length() - 1;
        int j = m.length - 1;

        while (i >= 0) {
            char ch = exp.charAt(i);
            if (ch >= 'A' && ch <= 'Z') {
                stack.push(m[j]);
                j--;
            } else if (ch == '(') {
                Matrix m1 = stack.pop();
                Matrix m2 = stack.pop();

                total += m1.x * m1.y * m2.y;
                Matrix m3 = new Matrix(m1.x, m2.y);
                stack.push(m3);
            }

            i--;
        }
        while (stack.size() >= 2) {
            Matrix m1 = stack.pop();
            Matrix m2 = stack.pop();

            total += m1.x * m1.y * m2.y;
            Matrix m3 = new Matrix(m1.x, m2.y);
            stack.push(m3);
        }

        return total;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int num = in.nextInt();
            Matrix[] m = new Matrix[num];

            for (int i = 0; i < num; i++) {
                int x = in.nextInt();
                int y = in.nextInt();
                m[i] = new Matrix(x, y);
            }
            String exp = in.next();

            int count = getCount(m, exp);
            System.out.println(count);
        }
    }

}
